/**
 * 第二种写法+优化
 * 第一种冒泡排序没有判断当前的遍历是否还有比较，有可能再第几遍遍历比较的时候，已经全部排完了，达成效果了。
 * 但程序不知道，还要把每遍遍历完成，导致性能和时间浪费
 * 3 38 5 44 15 36 26 27 2 46 4 19 47 48 50
 * 3 5 38 15 36 26 27 2 44 4 19 46 47 48 50
 * 3 5 15 36 26 27 2 38 4 19 44 46 47 48 50
 * 3 5 15 26 27 2 36 4 19 38 44 46 47 48 50
 * 3 5 15 26 2 27 4 19 36 38 44 46 47 48 50
 * 3 5 15 2 26 4 19 27 36 38 44 46 47 48 50
 * 3 5 2 15 4 19 26 27 36 38 44 46 47 48 50
 * 3 2 5 4 15 19 26 27 36 38 44 46 47 48 50
 * 2 3 4 5 15 19 26 27 36 38 44 46 47 48 50
 *
 * 问题1：通过打印每轮的排序结果，发现在第9轮排序的时候，已经达到了排序的效果，但后面5轮还在排序(最后一行是main里打印的），浪费时间和性能
 * 优化1：加个flag交换标志，如果某一轮都没发生交换，认为排序完成，跳出后面的排序循环
 * 问题2：每进行一轮排序，都会有一个当前轮最大的数字确定排在后面了，如第一轮选出第一大，第二轮选出第二大，但还进行了比较
 * 优化2：后面轮的排序循环，只排序前面length-轮数-1个未确定的数字顺序即可
 *
 * 我们优化两处，一处是排序循环的次数，一处是每轮排序的内部比较
 */
package com.test.sort;

public class BubbleSort2 {
    public static void main(String[] args) {
        int[] a = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
        compare(a);
        for (int j : a) {  //打印数组里面的元素
            System.out.print(j + " ");
        }
    }

    public static void compare(int[] arr) {

        for (int i = 0; i < arr.length-1; i++) {  //因为到最后一轮的时候，最前面的数肯定是最小的了，所以少排一轮
            boolean swap = false;  //定义一个交换标志，每轮排序前置为不交换，如果进入内循环有交换，则为ture，不会触发break跳出大循环
            //下面的内循环只是一轮排序，选出一轮排序中最大的一个，我们要排14轮，即和数组的长度一样的次数，才能全部排完
            for (int j = 0; j < arr.length-i-1; j++) { //每排到几轮，最后几位已经是排好序的，只排序前length-i-1位即可。
                if (arr[j] > arr[j+1]) {
                    swap = true;  //有交换，则swap为ture，不会触发外循环的break
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
            if(!swap) break;  //到达某一轮排序时，没有发生过交换，swap还是false，所以认为排序已经达到效果，不再进行后面的排序
            //每比较一轮，看下结果是什么样子
            for (int z = 0; z < arr.length; z++) {
                System.out.print(arr[z] + " ");
            }
            System.out.println();  //每打印完一轮，换行
        }
    }
}
